//Given two binary strings a and b, return their sum as a binary string. 
//
// 
// Example 1: 
// Input: a = "11", b = "1"
//Output: "100"
// Example 2: 
// Input: a = "1010", b = "1011"
//Output: "10101"
// 
// 
// Constraints: 
//
// 
// 1 <= a.length, b.length <= 104 
// a and b consist only of '0' or '1' characters. 
// Each string does not contain leading zeros except for the zero itself. 
// 
// Related Topics 数学 字符串 
// 👍 606 👎 0


package leetcode.editor.cn;

//Java：Add Binary
class P67AddBinary {
    public static void main(String[] args) {
        Solution solution = new P67AddBinary().new Solution();
        // TO TEST
        System.out.println(solution.addBinary("101111", "10"));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String addBinary(String a, String b) {
            if (a.length() < b.length()) {
                String temp = a;
                a = b;
                b = temp;
            }
            char add = '0';
            char[] arr = a.toCharArray();
            for (int i = a.length() - 1; i >= 0; i--) {
                char aCh = a.charAt(i);
                int j = i - ((a.length() - b.length()));
                if (j < 0) {
                    if (add == '1') {
                        if (aCh == '1') {
                            arr[i] = '0';
                        } else {
                            arr[i] = '1';
                            add = '0';
                            break;
                        }
                    } else {
                        break;
                    }
                } else {
                    char bCh = b.charAt(j);
                    if (aCh == '1' && bCh == '1') {
                        if (add == '1') {
                            arr[i] = '1';
                        } else {
                            arr[i] = '0';
                            add = '1';
                        }
                    } else if (aCh == '0' && bCh == '0') {
                        if (add == '1') {
                            arr[i] = '1';
                        } else {
                            arr[i] = '0';
                        }
                        add = '0';
                    } else if ((aCh == '1' || bCh == '1') && add == '1') {
                        add = '1';
                        arr[i] = '0';
                    } else if (aCh == '1' || bCh == '1') {
                        arr[i] = '1';
                    }
                }
            }
            if (add == '1') {
                return '1' + new String(arr);
            }
            return new String(arr);
        }
        public  String addBinaryTwo(String a, String b) {
            int aIn = Integer.parseInt(a);
            int bIn = Integer.parseInt(b);
            int c = aIn + bIn;
            StringBuilder sb = new StringBuilder();
            int next = 0;
            while (c != 0) {
                int temp = c % 10;
                if (temp == 2) {
                    if (next == 1) {
                        sb.insert(0, 1);
                    } else {
                        sb.insert(0, 0);
                    }
                    next = 1;
                } else if (temp == 1) {
                    if (next == 1) {
                        next = 1;
                        sb.insert(0, 0);
                    } else {
                        next = 0;
                        sb.insert(0, 1);
                    }

                } else {
                    if (next == 1) {
                        next = 0;
                        sb.insert(0, 1);
                    } else {
                        sb.insert(0, 0);
                    }

                }
                c = c / 10;

            }
            if (next == 1) {
                sb.insert(0, next);
            }
            return String.valueOf(sb);
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}